class Solution
{
public:
    int numberOfPaths(vector<vector<int>> &grid, int k)
    {
        int m = grid.size();
        int n = grid[0].size();

        // mnk维张量，第(i, j, l)元素表示路径走到(i,j)时余数为l的路径条数
        vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(k, 0)));
        dp[0][0][grid[0][0] % k] = 1;
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                for (int l = 0; l < k; ++l)
                {
                    if (i > 0)
                    {
                        dp[i][j][(l + grid[i][j]) % k] += dp[i - 1][j][l];
                        dp[i][j][(l + grid[i][j]) % k] %= 1000000007;
                    }
                    if (j > 0)
                    {
                        dp[i][j][(l + grid[i][j]) % k] += dp[i][j - 1][l];
                        dp[i][j][(l + grid[i][j]) % k] %= 1000000007;
                    }
                }
            }
        }
        return dp[m - 1][n - 1][0];
    }

    // 暴力解，超时
    int numberOfPaths(vector<vector<int>> &grid, int k, int x, int y, int currentSum)
    {
        currentSum += grid[x][y];
        if (x == grid.size() - 1 && y == grid[0].size() - 1)
        {
            if (currentSum % k == 0)
            {
                return 1;
            }
            else
            {
                return 0;
            }
        }
        else
        {
            int result = 0;
            if (x != grid.size() - 1)
            {
                result += numberOfPaths(grid, k, x + 1, y, currentSum);
            }
            if (y != grid[0].size() - 1)
            {
                result += numberOfPaths(grid, k, x, y + 1, currentSum);
            }
            return result % 1000000007;
        }
    }
};